Prior


Gbase<- function(num, mean=0, sigma=1){
return( rnorm(n=1, mean, sigma))
}
PUrn_sample<- function(n, alpha, Gbase){
#theta.1 sample from base measure
theta<- Gbase(1)
group_vec <- c(1)
for (i in 2:n){
#probability to sample from base measure
p1<- alpha/ (alpha + i-1)
#probability to sample from existing atoms
p2<- 1/ (alpha + i-1)
pvec<- c(p1, p2*group_vec)
# prob <- c(alpha/(length(count.vector)+alpha), count.vector/(length(count.vector)+M))
group_num<- sample(0:length(group_vec), prob=pvec, size=1)
if (group_num == 0){
#add new atom
theta <- c(theta, Gbase(1))
group_vec <- c(group_vec, 1)
}else{
#update existing group for group_vec
group_vec[group_num] = group_vec[group_num] + 1
}
}
return(list(theta=theta, group= group_vec))
}
alpha_0<-1
n<- 500
x<- PUrn_sample(n, alpha_0,Gbase)
k_groups<- x$group
weights<- c(k_groups/(alpha_0+n), alpha_0/(alpha_0+n))
df_weights <- data.frame(matrix(NA, nrow =length(weights), ncol =1))
df_weights$pw<-weights
df_weights$tr<-1:length(weights)
pl_weigths<- ggplot(df_weights, aes(x=tr, y=pw)) +
geom_segment( aes(x=tr,xend=tr,y=0,yend=pw)) +
geom_point( size=0.5, color="red", fill=alpha("blue", 0.3), alpha=0.4, shape=21, stroke=2)+ labs(title=paste0("Prior weights"))+
theme_bw() + theme(axis.text.x = element_text(angle = 0, hjust = 1,size = 10), strip.text = element_text(size = 15),legend.position = "top", plot.title = element_text(hjust = 0.5))
pl_weigths
df_weights <- data.frame(matrix(NA, nrow =length(weights), ncol =1))
df_weights$pw<-weights
df_weights$tr<-c(x$theta,20)
pl_weigths<- ggplot(df_weights, aes(x=tr, y=pw)) +
geom_segment( aes(x=tr,xend=tr,y=0,yend=pw)) +
geom_point( size=0.5, color="red", fill=alpha("blue", 0.3), alpha=0.4, shape=21, stroke=2)+ labs(title=paste0("Prior weights"))+
theme_bw() + theme(axis.text.x = element_text(angle = 0, hjust = 1,size = 10), strip.text = element_text(size = 15),legend.position = "top", plot.title = element_text(hjust = 0.5))
pl_weigths
PolyaUrnGenerator <- function(num, M, G0.generator) {
X.vector <- G0.generator(n = 1)
count.vector <- 1
for (i in 2:num){
prob <- c(M/(length(count.vector)+M), count.vector/(length(count.vector)+M))
category <- which(rmultinom(n=1, size=1,prob=prob)==1) - 1
if (category == 0){
X.vector <- c(X.vector, G0.generator(n = 1))
count.vector <- c(count.vector, 1)
}else{
count.vector[category] = count.vector[category] + 1
}
}
return(list(X.vector, count.vector))
}
## Define a Polya Urn sampler
PolyaUrnSampler <- function(n, M, cutoff, num = 10000, G0.generator=rnorm){
output <- matrix(NA, nrow = n, ncol = length(cutoff) + 1)
cutoff <- c(-Inf, cutoff, Inf)
for(i in 1:n){
PU.sample <- PolyaUrnGenerator(num=num, M=M, G0.generator=G0.generator)
for(j in 1:ncol(output)){
output[i,j] <- sum(PU.sample[[2]][intersect(which(PU.sample[[1]] > cutoff[j]), which(PU.sample[[1]] <= cutoff[j+1]))])/num
}
}
return(output)
}
##
x<- PolyaUrnGenerator(1,1,rnorm)
y<- PUrn_sample(1, 1, Gbase)
ks.test(f_approx$ecf, ecdf(X))
One-sample Kolmogorov-Smirnov test
data: f_approx$ecf
D = 0.79, p-value = 8.882e-16
alternative hypothesis: two-sided
Posterior_P_Urn_exact<- function(X,theta,i,alpha){
q_weights<- dnorm(X[i], theta)
r_weight<- alpha*dnorm(X[i], mean=0, sd=sqrt(2))
#sum should be one
num_norm<- sum(q_weights)+r_weight
q_weights_norm<- q_weights/num_norm
r_weight_norm<- r_weight/num_norm
label <- sample(0:length(theta),prob=c(r_weight_norm,q_weights_norm),size=1,replace=TRUE)
if (label==0){
theta_new<- rnorm(1, mean=X[i], sd=sqrt(1/2))
}
else{
theta_new <- theta[label]
}
}
sample<- gen_data(mu_vec=c(1,5),sigma_vec=rep(0.2, 2),ns=50,prob_vec=c(0.5,0.5))
X<- sample
theta.matrix <- matrix(NA, nrow = 10000, ncol = length(X))
alpha<-1
#weights.matrix <- matrix(NA, nrow = 100, ncol = length(X)+1)
theta.init<- runif(length(X),-3,3)
theta.matrix[1,] <- theta.init
for (i in 2:nrow(theta.matrix)){
theta_last<- theta.matrix[i-1,]
N <- length(X)
temp_theta <- c(theta_last, rep(NA, N))
for (j in 1:N){
temp_theta[N+j] <- Posterior_P_Urn_exact(X, temp_theta[(j+1):(j+N-1)],j,alpha)
}
theta_S<- temp_theta[(N+1):(N*2)]
theta.matrix[i,] <-theta_S
}
#burnin period
theta.final <- theta.matrix[5000:10000,]
xgrid <- seq(from= -10, to=2,length=50)
fgrid <- NULL
fbar.H <- function(xgrid,wh)
{ ## return a draw F ~ p(F | ...) (approx)
fx <- rep(0,length(xgrid))
for(h in 1:length(wh))
fx <- fx + dnorm(xgrid,m=wh[h],sd=1)
return(fx/length(wh))
}
gibbs.H <- function(n.iter=500){
xgrid <- seq(from= -10, to=10,length=50)
fgrid <- NULL
plot(density(X),xlab="X",ylab="Y",bty="l",type="l",xlim=c(-10, 10),ylim=c(0,1), main="")
for(iter in 1:nrow(theta.matrix)){
## record draw F ~ p(F | th,sig,y) (approx)
f <- fbar.H(xgrid,theta.matrix[iter,])
lines(xgrid,f,col=iter,lty=3)
fgrid <- rbind(fgrid,f)
}
## add overall average (= posterior mean) to the plot
fbar <- apply(fgrid,2,mean)
lines(xgrid,fbar,lwd=3,col=2)
}
Posterior_G<- function(n, alpha, Gbase, theta){
}
Approximation 1st order
\[\theta_{n} \mid \theta_{n-1},..\theta_1 \sim \frac{k_n \alpha}{n} H + \frac{1}{n} \sum_i^{k_n} (n_i - \alpha)\delta_{\theta^*_j}\]
Approximation 2nd order
\[\theta_{n} \mid \theta_{n-1},..\theta_1 \sim \frac{k_n \alpha + \beta_n}{n + \beta_n} H + \frac{1}{n + \beta_n} \sum_i^{k_n} (n_i - \alpha)\delta_{\theta^*_j}\]
For PY process \(\beta_n = \theta\)
polya_urn_model <- function(base_measure, N_ball, alpha) {
balls <- c()
for (i in 1:N_ball) {
if (runif(1) < alpha / (alpha + length(balls))) {
#Add a new ball color.
new_color <- base_measure()
balls <- c(balls, new_color)
} else {
#Pick out a ball from the urn, and add back a # ball of the same color
ball <- balls[sample(1:length(balls), 1)]
balls <- c(balls, ball)
} }
balls
}
alpha_vect <- c(1, 10, 100, 1000)
N_urns <- 3
sigma2 <- c(1,.4,.2)
N_draws <- 100
N_xaxis <- 200
x_axis <- seq(-3, 3, length = N_xaxis)
result <- NULL
for (alpha in alpha_vect) {
PU <- polya_urn_model(function() rnorm(1), N_draws, alpha)
for (u in 1:N_urns) {
res <- mapply(function(mean) dnorm(x_axis, rep(mean, N_xaxis),
rep(sigma2[u], N_xaxis)), PU)
res <- apply(res, 1, mean)
new_draw <- cbind(res, x_axis, alpha, sigma2[u])
result <- rbind(result, new_draw)
} }
result <- as.data.frame(result)
names(result) <- c("density", "x", "alpha", "sigma2")
DP_mixt <- qplot(data = result, y = density, x = x,
geom = c("line", "area")) +
facet_grid(alpha ~ sigma2, labeller =
label_bquote(rows = alpha == .(alpha),
cols = sigma^2 == .(sigma2))) +
aes(color = as.factor(alpha)) +
theme(legend.position = "none")
DP_mixt
Add a new chunk by clicking the Insert Chunk button on the toolbar or by pressing Cmd+Option+I.
When you save the notebook, an HTML file containing the code and output will be saved alongside it (click the Preview button or press Cmd+Shift+K to preview the HTML file).
The preview shows you a rendered HTML copy of the contents of the editor. Consequently, unlike Knit, Preview does not run any R code chunks. Instead, the output of the chunk when it was last run in the editor is displayed.
LS0tCnRpdGxlOiAiUiBOb3RlYm9vayIKb3V0cHV0OiBodG1sX25vdGVib29rCi0tLQoKCmBgYHtyIGxpYnMsIGVjaG89RkFMU0V9CnJtKGxpc3Q9bHMoKSkKI1BhY2thZ2VzIGZvciBnYW1tYSBmdW5jdGlvbiBlc3RpbWF0aW9uCmxpYnJhcnkocHJhY21hKQpsaWJyYXJ5KEJyb2JkaW5nbmFnKQpsaWJyYXJ5KGNvcHVsYSkKbGlicmFyeShwbG90bHkpCmxpYnJhcnkoZGlzdHJFeCkKCmBgYAoKIyAkVl97a259JCBmdW5jdGlvbnMgYW5kIFByaW9yIGNsdXN0ZXIgZGlzdHJpYnRpb24uCgpgYGB7ciBWX2tuIGZ1bmN0aW9ucyBhbmQgUHJpb3IgY2x1c3RlciBkaXN0cmlidGlvbiwgZWNobz1GQUxTRX0KCiMjIyMjIyMjIyMjIyMjIyBWIGZvciBQWSAvIERpciAvIE5HRyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIwp2X3B5PC0gZnVuY3Rpb24oa3ZhbCwgc2lnbWEsdGhldGEsbnBvaW50cyl7CiAgY192PC0xOihrdmFsLTEpCiAgdl9uazwtICh0aGV0YSArc2lnbWEqY192KQogIFZ1cDwtIHByb2Qodl9uaykKICBuX3ZlYzwtIDE6KG5wb2ludHMtMSkKICBWbG93PC0gcHJvZCh0aGV0YSArbl92ZWMpCiAgVl90X25rPC1WdXAvVmxvdwogIHJldHVybihWX3RfbmspCn0KCiMjIyMjIyMjIyMjIyMjIyBWIGZvciBOR0cjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMKdl9uZzwtIGZ1bmN0aW9uKGJldGEsIHNpZ21hLCBrdmFsLCBucG9pbnRzKXsKICBzdW08LTAKICBjb2VmX2xvdzwtYXMuYnJvYihnYW1tYShucG9pbnRzKSkKICBjb2VmX2hpZ2g8LWFzLmJyb2IoZXhwKGJldGEpKiBzaWdtYV4oa3ZhbC0xKSkKICBjb2VmPC0gY29lZl9oaWdoL2NvZWZfbG93CiAgaW5jdjwtIGFzLmJyb2IodmVjdG9yKGxlbmd0aD1ucG9pbnRzKSkKICBmb3IoaSBpbiAoMDoobnBvaW50cy0xKSkpewogICAgZ248LSBhcy5icm9iKGdhbW1haW5jKGt2YWwgLSBpL3NpZ21hLGJldGEpWzJdKQogICAgI2duPC0gZ2FtbWFfaW5jKGt2YWwgLSBpL3NpZ21hLGJldGEpCiAgICBja248LSBhcy5icm9iKGNob29zZShucG9pbnRzLTEsaSkpCiAgICBzdW08LSBzdW0gKyAoKC0xKV5pKSooYmV0YV4oaS9zaWdtYSkpKmNrbipnbgogICAgaW5jdltpKzFdPC0gZ24KICB9CiAgc3VtZjwtIHN1bS9jb2VmCiAgc3VtbjwtIGFzLm51bWVyaWMoc3VtZikKICByZXR1cm4obGlzdChzdW09c3VtZiwgaW5jZz0gaW5jdikpIAp9CgoKdl9uZzI8LSBmdW5jdGlvbihiZXRhLCBzaWdtYSwga3ZhbCwgbnBvaW50cyl7CiAgc3VtPC0wCiAgaW5jdjwtIGFzLmJyb2IodmVjdG9yKGxlbmd0aD1ucG9pbnRzKSkKICBmb3IoaSBpbiAoMDoobnBvaW50cy0xKSkpewogICAgY29lZl9sb3c8LWFzLmJyb2IoZ2FtbWEobnBvaW50cykpCiAgICBjb2VmX2hpZ2g8LWFzLmJyb2IoZXhwKGJldGEpKiBzaWdtYV4oa3ZhbC0xKSkKICAgIGNvZWY8LSBjb2VmX2hpZ2gvY29lZl9sb3cKICAgIGduPC0gYXMuYnJvYihnYW1tYWluYyhrdmFsIC0gaS9zaWdtYSxiZXRhKVsyXSkKICAgIGNrbjwtIGFzLmJyb2IoY2hvb3NlKG5wb2ludHMtMSxpKSkKICAgIHN1bTwtIHN1bSArICgoLTEpXmkpKihiZXRhXihpL3NpZ21hKSkqY2tuKmduKmNvZWYKICAgIGluY3ZbaSsxXTwtIGduCiAgfQogIHN1bWY8LSBzdW0KICBzdW1uPC0gYXMubnVtZXJpYyhzdW1mKQogIHJldHVybihsaXN0KHN1bT1zdW1uLCBpbmNnPSBpbmN2KSkgCn0KCiMjIyMjIyMjIyMjIyMjI0dlbmVyYWxpemVkIGNvZWZmaWNpZW50IyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjCgpnZW5fZmFjX2NvZWY8LWZ1bmN0aW9uKGt2YWwsc2lnbWEsbnBvaW50cyl7CiAgc3VtPC0wCiAga2ZhYzwtZmFjdG9yaWFsKGt2YWwpCiAgZm9yKGkgaW4gKDA6a3ZhbCkpewogICAgbl92ZWM8LSAwOihucG9pbnRzLTEpCiAgICBzbjwtIHByb2QoLWkqc2lnbWEgK25fdmVjKQogICAgY2tuPC0gY2hvb3NlKGt2YWwsaSkKICAgICNwcmludCgoLTEpXmkqY2tuKnNuKQogICAgc3VtPC0gc3VtICsgKCgtMSleaSkqY2tuKnNuIAogIH0KICBzdW1mPC0gc3VtL2tmYWMKICByZXR1cm4oc3VtZikKfQoKCiMjIyMjIyMjIyMjIGRlbnNpdHkgZm9yICBOR0cgIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMKcHJvYl9uZzwtIGZ1bmN0aW9uKGtnLCBzaWdtYSwgbnBvaW50cywgYmV0YSl7CiAgcGJfdl9hbGw8LSB2X25nMihiZXRhLCBzaWdtYSwga2csIG5wb2ludHMpCiAgcGJfdjwtYXMuYnJvYihwYl92X2FsbCRzdW0pCiAgcGJfZ2VuPC0gYXMuYnJvYihnZW5fZmFjX2NvZWYoa2csc2lnbWEsIG5wb2ludHMpKQogIHByb2I8LSAocGJfdipwYl9nZW4pLyhhcy5icm9iKHNpZ21hXmtnKSkKICBwcm9iX251bTwtIGFzLm51bWVyaWMocHJvYikKICByZXR1cm4ocHJvYl9udW0pCn0KCiMjIyMjIyMjIyMjIGRlbnNpdHkgZm9yIFBZIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMKCnByb2JfcHk8LSBmdW5jdGlvbihrZywgbnBvaW50cywgc2lnbWEsIHRoZXRhKXsKICBwYl92PC0gdl9weShrZyxzaWdtYSwgdGhldGEsbnBvaW50cykKICBwYl9nZW48LSBnZW5fZmFjX2NvZWYoa2csc2lnbWEsIG5wb2ludHMpCiAgcHJvYjwtIChwYl92KnBiX2dlbikvKHNpZ21hXmtnKQogIHJldHVybihwcm9iKQp9CgojIyMjIyMjIyMjIyBkZW5zaXR5IGZvciBEaXJpY2hsZXQjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIwpwcm9iX2RpcjwtIGZ1bmN0aW9uKGssIG5wb2ludHMsIHRoZXRhKXsKICBuX3ZlYzwtIDA6KG5wb2ludHMtMSkKICB0aGV0YV9uPC0gcHJvZCh0aGV0YSArbl92ZWMpCiAgcHJvYjwtICgodGhldGFeaykgKihhYnMoU3RpcmxpbmcxKG5wb2ludHMsaykpKSkvdGhldGFfbgogIHJldHVybihwcm9iKQp9Cgpwcm9iX2Rpcl9sYXJnZV9kaW08LSBmdW5jdGlvbihrLCBucG9pbnRzLCB0aGV0YSl7CiAgbl92ZWM8LWFzLmJyb2IoIDA6KG5wb2ludHMtMSkpCiAgdGhldGFfbjwtIHByb2QodGhldGEgK25fdmVjKQogIHN0aXI8LSBhcy5icm9iKGFicyhTdGlybGluZzEobnBvaW50cyxrKSkpCiAgcG93ZXJrPC0gYXMuYnJvYigodGhldGFeaykpCiAgcHJvYl9icm9iPC0gcG93ZXJrKihzdGlyL3RoZXRhX24pCiAgcHJvYjwtIGFzLm51bWVyaWMocHJvYl9icm9iKQogIHJldHVybihwcm9iKQp9CgojIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjCiNwcmliX25nKGtnLCBucG9pbnRzLCBzaWdtYSwgYmV0YSkKa192ZWM8LXNlcSgxLDUwLGJ5PTUpCnNpZ21hX3ZlYzwtc2VxKDAuMiwwLjgsIGJ5PTAuMSkKejwtIG91dGVyKGtfdmVjLHNpZ21hX3ZlYyxWZWN0b3JpemUocHJvYl9uZyksbnBvaW50cz01MCwgYmV0YT0xKQoKcDwtIHBsb3RfbHkoc2hvd3NjYWxlID0gVFJVRSkgJT4lCiAgYWRkX3N1cmZhY2UoeD1rX3ZlYywgeT1zaWdtYV92ZWMseiA9eiwgY21pbiA9IG1pbih6KSwgY21heCA9IG1heCh6KSxjb2xvcmJhcj1saXN0KHRpdGxlPSdQWScpLCBjb2xvcnNjYWxlID0gbGlzdChjKDAsMSksYygicmdiKDI1NSwxMTIsMTg0KSIsInJnYigxMjgsMCw2NCkiKSksb3BhY2l0eSA9IDAuOTgpICU+JQogIGxheW91dCh0aXRsZT0iUHJpb3IgZGlzdHJpYnV0aW9uIiwgc2NlbmUgPSBsaXN0KHhheGlzPSBsaXN0KHRpdGxlPSJLIikseWF4aXM9IGxpc3QodGl0bGU9InNpZ21hIiksemF4aXM9IGxpc3QodGl0bGU9Ik4iLHJhbmdlID0gYyhtaW4oeiksbWF4KHopKSkpKQpwCgpgYGAKCiMgRGF0YSBnZW5lcmF0aW9uCgpHYXVzc2lhbiBtaXh0dXJlOgoKJCRZIFxzaW0gXGZyYWN7MX17Mn1OKDEsMC4yKSArXGZyYWN7MX17Mn1OKDUsMC4yKSQkCgpgYGB7ciBkYXRhIGdlbmVyYXRpb259Cmdlbl9kYXRhPC0gZnVuY3Rpb24obXVfdmVjPWMoMSw1LDMsNSksIHNpZ21hX3ZlYz1yZXAoMC4xLCA0KSwgbnM9NTAsIHByb2JfdmVjPWMoMC4yNSwwLjI1LDAuMjUsMC4yNSkgKXsKICBsPC0gbGVuZ3RoKG11X3ZlYykKICBjb21wb25lbnRzIDwtIHNhbXBsZSgxOmwscHJvYj1wcm9iX3ZlYyxzaXplPW5zLHJlcGxhY2U9VFJVRSkKICBtdXMgPC0gbXVfdmVjCiAgc2RzIDwtIHNxcnQoc2lnbWFfdmVjKQogIHNhbXBsZXMgPC0gcm5vcm0obj1ucyxtZWFuPW11c1tjb21wb25lbnRzXSxzZD1zZHNbY29tcG9uZW50c10pCiAgcmV0dXJuKHNhbXBsZXMpCn0KCnNldC5zZWVkKDEyMykKc2FtcGxlPC0gZ2VuX2RhdGEobXVfdmVjPWMoMSwxMCksc2lnbWFfdmVjPXJlcCgwLjIsIDIpLG5zPTEwMDAwLHByb2JfdmVjPWMoMC41LDAuNSkpCmhpc3Qoc2FtcGxlLHByb2JhYmlsaXR5PVRSVUUsYnJlYWtzPTIwLGNvbD1ncmV5KC45KSkKCgpgYGAKCgojIE1vZGVsIAoKXGJlZ2lue2VxdWF0aW9ufQpcYmVnaW57YWxpZ25lZH0KKFhfaSBcbWlkIChcbXVfaSxcdGF1X2kpKSAmXHN0YWNrcmVse2lpZH17XHNpbX0gTihcbXVfaSxcdGF1X2leey0xfSlcXAooKFxtdV9pLCBcdGF1X2kpIFxtaWQgRykgJlxzdGFja3JlbHtpaWR9e1xzaW19IEcgXFwKRyAmXHNpbSBcbWF0aGNhbHtQfSAuClxlbmR7YWxpZ25lZH0KXGVuZHtlcXVhdGlvbn0KCgoKRmlyc3RseSwgYXNzdW1lICRcdGF1X2k9MSQsdGhlbiB3ZSBoYXZlICRYX2kgXHNpbSBOKFxtdV9pLCAxKSQsIGJhc2UgbWVhc3VyZSAkR18wID0gTigwLDEpJCwgJFlfaT0gKFxtdV9pKSQuIEZvciBzYW1wbGluZyB3ZSB1c2UgUG9seWEgVXJuIGNoYXJhY3Rlcml6YXRpb24KClxiZWdpbntlcXVhdGlvbn0KICAgICBwKFlfaSB8IHtZX3staX19KSA9IFxmcmFje1xhbHBoYX17XGFscGhhK24tMX0gR18wICsgXGZyYWN7MX17XGFscGhhICsgbiAtMX0gXHN1bV97aj0xfV57bi0xfSBcZGVsdGFfe1lfan0gXHFxdWFkIFxmb3JhbGwgaT0xLFxsZG90cyAsbi4KXGVuZHtlcXVhdGlvbn0KCgoKR2liYnMgc2FtcGxlcjoKXGJlZ2lue2VxdWF0aW9ufQpcYmVnaW57YWxpZ25lZH0KRyAmXG1pZCBcdGhldGEsIFggXHNpbSBEUChcYWxwaGEgK24sXGZyYWN7XGFscGhhfXsoXGFscGhhICsgbil9IEdfMCArIFxmcmFjezF9e1xhbHBoYSArIG4pfVxzdW1faiBcZGVsdGFfe1x0aGV0YV9qKX1cXApcdGhldGFfaSAmXG1pZCBcdGhldGFfey1pfSxYLCBHIFxzaW0gXHN1bV97alxuZXEgaX1xX3tpan0gXGRlbHRhX3tcdGhldGFfan0gKyByX2kgRyBcXApxX3tpan0gJj0gYiBOKHhfLFx0aGV0YV9qKVxcCnJfaSAmPSAgYlxhbHBoYSBcaW50IGYoeF9pLCBcdGhldGEpZEdfMChcdGhldGEpLCBcdGV4dHtIZXJlOiB9IE4oeF9pLCBcdGhldGEsMSlOKFx0aGV0YSwgMCwxKVxwcm9wdG8gTih4X2kvMiwgMS8yKS5cXAoKXGVuZHthbGlnbmVkfQpcZW5ke2VxdWF0aW9ufQoKCiNQcmlvcgoKYGBge3IgbWl4dHVyZX0KCkdiYXNlPC0gZnVuY3Rpb24obnVtLCBtZWFuPTAsIHNpZ21hPTEpewogIHJldHVybiggcm5vcm0obj0xLCBtZWFuLCBzaWdtYSkpCn0KCgoKUFVybl9zYW1wbGU8LSAgZnVuY3Rpb24obiwgYWxwaGEsIEdiYXNlKXsKICAjdGhldGEuMSBzYW1wbGUgZnJvbSBiYXNlIG1lYXN1cmUKICAgdGhldGE8LSBHYmFzZSgxKQogICBncm91cF92ZWMgPC0gYygxKQogICBmb3IgKGkgaW4gMjpuKXsKICAgICAjcHJvYmFiaWxpdHkgdG8gc2FtcGxlIGZyb20gYmFzZSBtZWFzdXJlCiAgICAgcDE8LSBhbHBoYS8gKGFscGhhICsgaS0xKQogICAgICNwcm9iYWJpbGl0eSB0byBzYW1wbGUgZnJvbSBleGlzdGluZyBhdG9tcwogICAgIHAyPC0gMS8gKGFscGhhICsgaS0xKQogICAgIHB2ZWM8LSBjKHAxLCBwMipncm91cF92ZWMpCiAgICAjIHByb2IgPC0gYyhhbHBoYS8obGVuZ3RoKGNvdW50LnZlY3RvcikrYWxwaGEpLCBjb3VudC52ZWN0b3IvKGxlbmd0aChjb3VudC52ZWN0b3IpK00pKQogICAgZ3JvdXBfbnVtPC0gIHNhbXBsZSgwOmxlbmd0aChncm91cF92ZWMpLCBwcm9iPXB2ZWMsIHNpemU9MSkKCiAgICBpZiAoZ3JvdXBfbnVtID09IDApewogICAgICAjYWRkIG5ldyBhdG9tCiAgICAgIHRoZXRhIDwtIGModGhldGEsIEdiYXNlKDEpKQogICAgICBncm91cF92ZWMgPC0gYyhncm91cF92ZWMsIDEpCiAgICB9ZWxzZXsKICAgICAgI3VwZGF0ZSBleGlzdGluZyBncm91cCBmb3IgZ3JvdXBfdmVjCiAgICAgIGdyb3VwX3ZlY1tncm91cF9udW1dID0gZ3JvdXBfdmVjW2dyb3VwX251bV0gKyAxCiAgICB9CiAgfQogIHJldHVybihsaXN0KHRoZXRhPXRoZXRhLCBncm91cD0gZ3JvdXBfdmVjKSkKfQphbHBoYV8wPC0xCm48LSA1MDAKeDwtIFBVcm5fc2FtcGxlKG4sIGFscGhhXzAsR2Jhc2UpCmtfZ3JvdXBzPC0geCRncm91cAp3ZWlnaHRzPC0gYyhrX2dyb3Vwcy8oYWxwaGFfMCtuKSwgYWxwaGFfMC8oYWxwaGFfMCtuKSkKICAKZGZfd2VpZ2h0cyA8LSBkYXRhLmZyYW1lKG1hdHJpeChOQSwgbnJvdyA9bGVuZ3RoKHdlaWdodHMpLCBuY29sID0xKSkKZGZfd2VpZ2h0cyRwdzwtd2VpZ2h0cwpkZl93ZWlnaHRzJHRyPC0xOmxlbmd0aCh3ZWlnaHRzKQpwbF93ZWlndGhzPC0gZ2dwbG90KGRmX3dlaWdodHMsIGFlcyh4PXRyLCB5PXB3KSkgKwogIGdlb21fc2VnbWVudCggYWVzKHg9dHIseGVuZD10cix5PTAseWVuZD1wdykpICsKICBnZW9tX3BvaW50KCBzaXplPTAuNSwgY29sb3I9InJlZCIsIGZpbGw9YWxwaGEoImJsdWUiLCAwLjMpLCBhbHBoYT0wLjQsIHNoYXBlPTIxLCBzdHJva2U9MikrICBsYWJzKHRpdGxlPXBhc3RlMCgiUHJpb3Igd2VpZ2h0cyIpKSsKICB0aGVtZV9idygpICsgdGhlbWUoYXhpcy50ZXh0LnggPSBlbGVtZW50X3RleHQoYW5nbGUgPSAwLCBoanVzdCA9IDEsc2l6ZSA9IDEwKSwgc3RyaXAudGV4dCA9IGVsZW1lbnRfdGV4dChzaXplID0gMTUpLGxlZ2VuZC5wb3NpdGlvbiA9ICJ0b3AiLCBwbG90LnRpdGxlID0gZWxlbWVudF90ZXh0KGhqdXN0ID0gMC41KSkKcGxfd2VpZ3RocwoKCmRmX3dlaWdodHMgPC0gZGF0YS5mcmFtZShtYXRyaXgoTkEsIG5yb3cgPWxlbmd0aCh3ZWlnaHRzKSwgbmNvbCA9MSkpCmRmX3dlaWdodHMkcHc8LXdlaWdodHMKZGZfd2VpZ2h0cyR0cjwtYyh4JHRoZXRhLDIwKQpwbF93ZWlndGhzPC0gZ2dwbG90KGRmX3dlaWdodHMsIGFlcyh4PXRyLCB5PXB3KSkgKwogIGdlb21fc2VnbWVudCggYWVzKHg9dHIseGVuZD10cix5PTAseWVuZD1wdykpICsKICBnZW9tX3BvaW50KCBzaXplPTAuNSwgY29sb3I9InJlZCIsIGZpbGw9YWxwaGEoImJsdWUiLCAwLjMpLCBhbHBoYT0wLjQsIHNoYXBlPTIxLCBzdHJva2U9MikrICBsYWJzKHRpdGxlPXBhc3RlMCgiUHJpb3Igd2VpZ2h0cyIpKSsKICB0aGVtZV9idygpICsgdGhlbWUoYXhpcy50ZXh0LnggPSBlbGVtZW50X3RleHQoYW5nbGUgPSAwLCBoanVzdCA9IDEsc2l6ZSA9IDEwKSwgc3RyaXAudGV4dCA9IGVsZW1lbnRfdGV4dChzaXplID0gMTUpLGxlZ2VuZC5wb3NpdGlvbiA9ICJ0b3AiLCBwbG90LnRpdGxlID0gZWxlbWVudF90ZXh0KGhqdXN0ID0gMC41KSkKcGxfd2VpZ3RocwoKCiBQb2x5YVVybkdlbmVyYXRvciA8LSBmdW5jdGlvbihudW0sIE0sIEcwLmdlbmVyYXRvcikgewogICBYLnZlY3RvciA8LSBHMC5nZW5lcmF0b3IobiA9IDEpCiAgIGNvdW50LnZlY3RvciA8LSAxCiAgIGZvciAoaSBpbiAyOm51bSl7CiAgICAgcHJvYiA8LSBjKE0vKGxlbmd0aChjb3VudC52ZWN0b3IpK00pLCBjb3VudC52ZWN0b3IvKGxlbmd0aChjb3VudC52ZWN0b3IpK00pKQogICAgIGNhdGVnb3J5IDwtIHdoaWNoKHJtdWx0aW5vbShuPTEsIHNpemU9MSxwcm9iPXByb2IpPT0xKSAtIDEKICAgICBpZiAoY2F0ZWdvcnkgPT0gMCl7CiAgICAgICBYLnZlY3RvciA8LSBjKFgudmVjdG9yLCBHMC5nZW5lcmF0b3IobiA9IDEpKQogICAgICAgY291bnQudmVjdG9yIDwtIGMoY291bnQudmVjdG9yLCAxKQogICAgIH1lbHNlewogICAgICAgY291bnQudmVjdG9yW2NhdGVnb3J5XSA9IGNvdW50LnZlY3RvcltjYXRlZ29yeV0gKyAxCiAgICAgfQogICB9CiAgIHJldHVybihsaXN0KFgudmVjdG9yLCBjb3VudC52ZWN0b3IpKQogfQoKCiMjIERlZmluZSBhIFBvbHlhIFVybiBzYW1wbGVyClBvbHlhVXJuU2FtcGxlciA8LSBmdW5jdGlvbihuLCBNLCBjdXRvZmYsIG51bSA9IDEwMDAwLCBHMC5nZW5lcmF0b3I9cm5vcm0pewogIG91dHB1dCA8LSBtYXRyaXgoTkEsIG5yb3cgPSBuLCBuY29sID0gbGVuZ3RoKGN1dG9mZikgKyAxKQogIGN1dG9mZiA8LSBjKC1JbmYsIGN1dG9mZiwgSW5mKQogIGZvcihpIGluIDE6bil7CiAgICBQVS5zYW1wbGUgPC0gUG9seWFVcm5HZW5lcmF0b3IobnVtPW51bSwgTT1NLCBHMC5nZW5lcmF0b3I9RzAuZ2VuZXJhdG9yKQogICAgZm9yKGogaW4gMTpuY29sKG91dHB1dCkpewogICAgICBvdXRwdXRbaSxqXSA8LSBzdW0oUFUuc2FtcGxlW1syXV1baW50ZXJzZWN0KHdoaWNoKFBVLnNhbXBsZVtbMV1dID4gY3V0b2ZmW2pdKSwgd2hpY2goUFUuc2FtcGxlW1sxXV0gPD0gY3V0b2ZmW2orMV0pKV0pL251bQogICAgfQogIH0KICByZXR1cm4ob3V0cHV0KQp9CgojIyAKeDwtIFBvbHlhVXJuR2VuZXJhdG9yKDEsMSxybm9ybSkKeTwtIFBVcm5fc2FtcGxlKDEsIDEsIEdiYXNlKQoKYGBgCgoKCgoKYGBge3IgR2liYnMgdGhldGF9ClBvc3Rlcmlvcl9QX1Vybl9leGFjdDwtIGZ1bmN0aW9uKFgsdGhldGEsaSxhbHBoYSl7CiAgcV93ZWlnaHRzPC0gZG5vcm0oWFtpXSwgdGhldGEpCiAgcl93ZWlnaHQ8LSBhbHBoYSpkbm9ybShYW2ldLCBtZWFuPTAsIHNkPXNxcnQoMikpCiAgI3N1bSBzaG91bGQgYmUgb25lCiAgbnVtX25vcm08LSBzdW0ocV93ZWlnaHRzKStyX3dlaWdodAogIHFfd2VpZ2h0c19ub3JtPC0gcV93ZWlnaHRzL251bV9ub3JtCiAgcl93ZWlnaHRfbm9ybTwtIHJfd2VpZ2h0L251bV9ub3JtCiAgbGFiZWwgPC0gc2FtcGxlKDA6bGVuZ3RoKHRoZXRhKSxwcm9iPWMocl93ZWlnaHRfbm9ybSxxX3dlaWdodHNfbm9ybSksc2l6ZT0xLHJlcGxhY2U9VFJVRSkKICBpZiAobGFiZWw9PTApewogICAgdGhldGFfbmV3PC0gcm5vcm0oMSwgbWVhbj1YW2ldLCBzZD1zcXJ0KDEvMikpCiAgfQogIGVsc2V7CiAgICB0aGV0YV9uZXcgPC0gdGhldGFbbGFiZWxdCiAgfQp9CgoKc2FtcGxlPC0gZ2VuX2RhdGEobXVfdmVjPWMoMSwxMCksc2lnbWFfdmVjPXJlcCgwLjIsIDIpLG5zPTEwMCxwcm9iX3ZlYz1jKDAuNSwwLjUpKQpYPC0gc2FtcGxlCnRoZXRhLm1hdHJpeCA8LSBtYXRyaXgoTkEsIG5yb3cgPSAxMDAwMCwgbmNvbCA9IGxlbmd0aChYKSkKYWxwaGE8LTEKI3dlaWdodHMubWF0cml4IDwtIG1hdHJpeChOQSwgbnJvdyA9IDEwMCwgbmNvbCA9IGxlbmd0aChYKSsxKQp0aGV0YS5pbml0PC0gcnVuaWYobGVuZ3RoKFgpLC0zLDMpCnRoZXRhLm1hdHJpeFsxLF0gPC0gdGhldGEuaW5pdApmb3IgKGkgaW4gMjpucm93KHRoZXRhLm1hdHJpeCkpewogICAgdGhldGFfbGFzdDwtIHRoZXRhLm1hdHJpeFtpLTEsXQogICAgTiA8LSBsZW5ndGgoWCkKICAgIHRlbXBfdGhldGEgPC0gYyh0aGV0YV9sYXN0LCByZXAoTkEsIE4pKSAKICAgIGZvciAoaiBpbiAxOk4pewogICAgICB0ZW1wX3RoZXRhW04ral0gPC0gUG9zdGVyaW9yX1BfVXJuX2V4YWN0KFgsIHRlbXBfdGhldGFbKGorMSk6KGorTi0xKV0saixhbHBoYSkKICAgIH0KICAgIHRoZXRhX1M8LSB0ZW1wX3RoZXRhWyhOKzEpOihOKjIpXQogICAgdGhldGEubWF0cml4W2ksXSA8LXRoZXRhX1MKfQoKI2J1cm5pbiBwZXJpb2QKdGhldGEuZmluYWwgPC0gdGhldGEubWF0cml4WzUwMDA6MTAwMDAsXSAKIAojeGdyaWQgPC0gc2VxKGZyb209IC01LCB0bz0xNSxsZW5ndGg9MTAwKQojZmdyaWQgPC0gTlVMTAoKZmJhci5IIDwtIGZ1bmN0aW9uKHhncmlkLHdoKQp7ICMjIHJldHVybiBhIGRyYXcgRiB+IHAoRiB8IC4uLikgKGFwcHJveCkKICAKICBmeCA8LSByZXAoMCxsZW5ndGgoeGdyaWQpKQogIGZvcihoIGluIDE6bGVuZ3RoKHdoKSkKICAgIGZ4IDwtIGZ4ICsgZG5vcm0oeGdyaWQsbT13aFtoXSxzZD0xKQogIGZ4PC0gZnggKyAgTS8obitNKSpkbm9ybSh4Z3JpZCxtPW0wLHNkPXNxcnQoQjArc2lnKSkKICByZXR1cm4oZngvbGVuZ3RoKHdoKSkKfQoKCmZiYXIuSF9iYXNlIDwtIGZ1bmN0aW9uKHhncmlkLHdoKQp7ICMjIHJldHVybiBhIGRyYXcgRiB+IHAoRiB8IC4uLikgKGFwcHJveCkKICBmeCA8LSByZXAoMCxsZW5ndGgoeGdyaWQpKQogIGZvcihoIGluIDE6bGVuZ3RoKHdoKSl7CiAgICBmeCA8LSBmeCArIGRub3JtKHhncmlkLG09d2hbaF0sc2Q9MSkgCiAgfQogIGZ4X208LSBmeC8gKGxlbmd0aCh3aCkrIGFscGhhKQogIGZ4X208LSBmeF9tICsgIGFscGhhLyhsZW5ndGgod2gpK2FscGhhKSpkbm9ybSh4Z3JpZCxtPTAsc2Q9c3FydCgyKSkKICByZXR1cm4oZnhfbSkKfQoKCgplY2ZiYXIuSF9iYXNlIDwtIGZ1bmN0aW9uKHhncmlkLHdoKQp7ICMjIHJldHVybiBhIGRyYXcgRiB+IHAoRiB8IC4uLikgKGFwcHJveCkKICAKICBmeCA8LSByZXAoMCxsZW5ndGgoeGdyaWQpKQogIGZvcihoIGluIDE6bGVuZ3RoKHdoKSl7CiAgICBmeCA8LSBmeCArIHBub3JtKHhncmlkLG09d2hbaF0sc2Q9MSkgCiAgfQogIGZ4X208LSBmeC8gKGxlbmd0aCh3aCkrIGFscGhhKQogIGZ4X208LSBmeF9tICsgIGFscGhhLyhsZW5ndGgod2gpK2FscGhhKSpwbm9ybSh4Z3JpZCxtPTAsc2Q9c3FydCgyKSkKICByZXR1cm4oZnhfbSkKfQoKCmdpYmJzLkggPC0gZnVuY3Rpb24obi5pdGVyPTEwMDAwKXsKICB4Z3JpZCA8LSBzZXEoZnJvbT0gLTUsIHRvPTEyLGxlbmd0aD01MCkKICBjZ3JpZDwtIHNlcShmcm9tPSAtNSwgdG89MTUsbGVuZ3RoPTUwKQogIGZncmlkIDwtIE5VTEwKICBlY2ZncmlkIDwtIE5VTEwKICBwbG90KGRlbnNpdHkoWCkseGxhYj0iWCIseWxhYj0iWSIsYnR5PSJsIix0eXBlPSJsIix4bGltPWMoLTUsIDE1KSx5bGltPWMoMCwxKSwgbWFpbj0iIikKICBmb3IoaXRlciBpbiAxOm5yb3codGhldGEuZmluYWwpKXsKICAgICAgIyMgcmVjb3JkIGRyYXcgRiB+IHAoRiB8IHRoLHNpZyx5KSAoYXBwcm94KQogICAgICBmICAgPC0gZmJhci5IX2Jhc2UoeGdyaWQsdGhldGEuZmluYWxbaXRlcixdKQogICAgICBsaW5lcyh4Z3JpZCxmLGNvbD1pdGVyLGx0eT0zKQogICAgICBmZ3JpZCA8LSByYmluZChmZ3JpZCxmKQogICAgfQogICAgIyMgYWRkIG92ZXJhbGwgYXZlcmFnZSAoPSBwb3N0ZXJpb3IgbWVhbikgdG8gdGhlIHBsb3QKICAgIGZiYXIgPC0gYXBwbHkoZmdyaWQsMixtZWFuKQogICAgbGluZXMoeGdyaWQsZmJhcixsd2Q9Myxjb2w9MikKICAgIHBsb3QoZWNkZihYKSx4bGFiPSJYIix5bGFiPSJZIixidHk9ImwiLCBtYWluPSIiKQogIGZvcihpdGVyIGluIDE6bnJvdyh0aGV0YS5maW5hbCkpewogICAgICAjIyByZWNvcmQgZHJhdyBGIH4gcChGIHwgdGgsc2lnLHkpIChhcHByb3gpCiAgICAgIGVjZjwtIGVjZmJhci5IX2Jhc2UoY2dyaWQsdGhldGEuZmluYWxbaXRlcixdKQogICAgICBsaW5lcyhjZ3JpZCxlY2YsY29sPWl0ZXIsbHR5PTMpCiAgICAgIGVjZmdyaWQgPC0gcmJpbmQoZWNmZ3JpZCxlY2YpCiAgICB9CiAgICAjIyBhZGQgb3ZlcmFsbCBhdmVyYWdlICg9IHBvc3RlcmlvciBtZWFuKSB0byB0aGUgcGxvdAogICAgZmJhciA8LSBhcHBseShmZ3JpZCwyLG1lYW4pCiAgICBlY2ZiYXI8LSBhcHBseShlY2ZncmlkLDIsbWVhbikKICAgIGxpbmVzKGNncmlkLGVjZmJhcixsd2Q9Myxjb2w9MikKICAgIAogICAgcmV0dXJuKGxpc3QoZl9hcD1mYmFyLCBlY2Y9ZWNmYmFyKSkKfQoKCmZfYXBwcm94PC0gZ2liYnMuSCgpCmtzLnRlc3QoZl9hcHByb3gkZWNmLCBlY2RmKFgpKQoKYGBgCgoKCgoKCgoKCgpgYGB7ciBHaWJicyB0aGV0YSBhcHByb3h9ClBvc3Rlcmlvcl9QX1Vybl9leGFjdDwtIGZ1bmN0aW9uKFgsdGhldGEsaSxhbHBoYSl7CiAgcV93ZWlnaHRzPC0gZG5vcm0oWFtpXSwgdGhldGEpCiAgcl93ZWlnaHQ8LSBhbHBoYSpkbm9ybShYW2ldLCBtZWFuPTAsIHNkPXNxcnQoMikpCiAgI3N1bSBzaG91bGQgYmUgb25lCiAgbnVtX25vcm08LSBzdW0ocV93ZWlnaHRzKStyX3dlaWdodAogIHFfd2VpZ2h0c19ub3JtPC0gcV93ZWlnaHRzL251bV9ub3JtCiAgcl93ZWlnaHRfbm9ybTwtIHJfd2VpZ2h0L251bV9ub3JtCiAgbGFiZWwgPC0gc2FtcGxlKDA6bGVuZ3RoKHRoZXRhKSxwcm9iPWMocl93ZWlnaHRfbm9ybSxxX3dlaWdodHNfbm9ybSksc2l6ZT0xLHJlcGxhY2U9VFJVRSkKICBpZiAobGFiZWw9PTApewogICAgdGhldGFfbmV3PC0gcm5vcm0oMSwgbWVhbj1YW2ldLCBzZD1zcXJ0KDEvMikpCiAgfQogIGVsc2V7CiAgICB0aGV0YV9uZXcgPC0gdGhldGFbbGFiZWxdCiAgfQp9CgoKc2FtcGxlPC0gZ2VuX2RhdGEobXVfdmVjPWMoMSw1KSxzaWdtYV92ZWM9cmVwKDAuMiwgMiksbnM9NTAscHJvYl92ZWM9YygwLjUsMC41KSkKWDwtIHNhbXBsZQp0aGV0YS5tYXRyaXggPC0gbWF0cml4KE5BLCBucm93ID0gMTAwMDAsIG5jb2wgPSBsZW5ndGgoWCkpCmFscGhhPC0xCiN3ZWlnaHRzLm1hdHJpeCA8LSBtYXRyaXgoTkEsIG5yb3cgPSAxMDAsIG5jb2wgPSBsZW5ndGgoWCkrMSkKdGhldGEuaW5pdDwtIHJ1bmlmKGxlbmd0aChYKSwtMywzKQp0aGV0YS5tYXRyaXhbMSxdIDwtIHRoZXRhLmluaXQKZm9yIChpIGluIDI6bnJvdyh0aGV0YS5tYXRyaXgpKXsKICAgIHRoZXRhX2xhc3Q8LSB0aGV0YS5tYXRyaXhbaS0xLF0KICAgIE4gPC0gbGVuZ3RoKFgpCiAgICB0ZW1wX3RoZXRhIDwtIGModGhldGFfbGFzdCwgcmVwKE5BLCBOKSkgCiAgICBmb3IgKGogaW4gMTpOKXsKICAgICAgdGVtcF90aGV0YVtOK2pdIDwtIFBvc3Rlcmlvcl9QX1Vybl9leGFjdChYLCB0ZW1wX3RoZXRhWyhqKzEpOihqK04tMSldLGosYWxwaGEpCiAgICB9CiAgICB0aGV0YV9TPC0gdGVtcF90aGV0YVsoTisxKTooTioyKV0KICAgIHRoZXRhLm1hdHJpeFtpLF0gPC10aGV0YV9TCn0KCiNidXJuaW4gcGVyaW9kCnRoZXRhLmZpbmFsIDwtIHRoZXRhLm1hdHJpeFs1MDAwOjEwMDAwLF0gCiAKeGdyaWQgPC0gc2VxKGZyb209IC0xMCwgdG89MixsZW5ndGg9NTApCmZncmlkIDwtIE5VTEwKCmZiYXIuSCA8LSBmdW5jdGlvbih4Z3JpZCx3aCkKeyAjIyByZXR1cm4gYSBkcmF3IEYgfiBwKEYgfCAuLi4pIChhcHByb3gpCiAgCiAgZnggPC0gcmVwKDAsbGVuZ3RoKHhncmlkKSkKICBmb3IoaCBpbiAxOmxlbmd0aCh3aCkpCiAgICBmeCA8LSBmeCArIGRub3JtKHhncmlkLG09d2hbaF0sc2Q9MSkKICByZXR1cm4oZngvbGVuZ3RoKHdoKSkKfQoKCmdpYmJzLkggPC0gZnVuY3Rpb24obi5pdGVyPTUwMCl7CnhncmlkIDwtIHNlcShmcm9tPSAtMTAsIHRvPTEwLGxlbmd0aD01MCkKZmdyaWQgPC0gTlVMTApwbG90KGRlbnNpdHkoWCkseGxhYj0iWCIseWxhYj0iWSIsYnR5PSJsIix0eXBlPSJsIix4bGltPWMoLTEwLCAxMCkseWxpbT1jKDAsMSksIG1haW49IiIpCmZvcihpdGVyIGluIDE6bnJvdyh0aGV0YS5tYXRyaXgpKXsKICAgICMjIHJlY29yZCBkcmF3IEYgfiBwKEYgfCB0aCxzaWcseSkgKGFwcHJveCkKICAgIGYgICA8LSBmYmFyLkgoeGdyaWQsdGhldGEubWF0cml4W2l0ZXIsXSkKICAgIGxpbmVzKHhncmlkLGYsY29sPWl0ZXIsbHR5PTMpCiAgICBmZ3JpZCA8LSByYmluZChmZ3JpZCxmKQogIH0KICAjIyBhZGQgb3ZlcmFsbCBhdmVyYWdlICg9IHBvc3RlcmlvciBtZWFuKSB0byB0aGUgcGxvdAogIGZiYXIgPC0gYXBwbHkoZmdyaWQsMixtZWFuKQogIGxpbmVzKHhncmlkLGZiYXIsbHdkPTMsY29sPTIpCn0KCgoKYGBgCgoKCgoKCgoKCgpgYGB7ciBHaWJicyBwb3N0ZXJpb3Igd2VpZ2h0c30KClBvc3Rlcmlvcl9HPC0gZnVuY3Rpb24obiwgYWxwaGEsIEdiYXNlLCB0aGV0YSl7CiAgCn0KCmBgYAoKCgpBcHByb3hpbWF0aW9uIDFzdCBvcmRlcgoKJCRcdGhldGFfe259IFxtaWQgXHRoZXRhX3tuLTF9LC4uXHRoZXRhXzEgXHNpbSBcZnJhY3trX24gXGFscGhhfXtufSBIICsgXGZyYWN7MX17bn0gXHN1bV9pXntrX259IChuX2kgLSBcYWxwaGEpXGRlbHRhX3tcdGhldGFeKl9qfSQkCgoKQXBwcm94aW1hdGlvbiAybmQgb3JkZXIKCiQkXHRoZXRhX3tufSBcbWlkIFx0aGV0YV97bi0xfSwuLlx0aGV0YV8xIFxzaW0gXGZyYWN7a19uIFxhbHBoYSArIFxiZXRhX259e24gKyBcYmV0YV9ufSBIICsgXGZyYWN7MX17biArIFxiZXRhX259IFxzdW1faV57a19ufSAobl9pIC0gXGFscGhhKVxkZWx0YV97XHRoZXRhXipfan0kJAoKRm9yIFBZIHByb2Nlc3MgJFxiZXRhX24gPSBcdGhldGEkCgoKCgoKCgpgYGB7cn0KCgpwb2x5YV91cm5fbW9kZWwgPC0gZnVuY3Rpb24oYmFzZV9tZWFzdXJlLCBOX2JhbGwsIGFscGhhKSB7CiAgYmFsbHMgPC0gYygpCiAgZm9yIChpIGluIDE6Tl9iYWxsKSB7CiAgICBpZiAocnVuaWYoMSkgPCBhbHBoYSAvIChhbHBoYSArIGxlbmd0aChiYWxscykpKSB7IAogICAgICAjQWRkIGEgbmV3IGJhbGwgY29sb3IuCiAgICAgIG5ld19jb2xvciA8LSBiYXNlX21lYXN1cmUoKQogICAgICBiYWxscyA8LSBjKGJhbGxzLCBuZXdfY29sb3IpCiAgICAgICAgfSBlbHNlIHsKICAgICNQaWNrIG91dCBhIGJhbGwgZnJvbSB0aGUgdXJuLCBhbmQgYWRkIGJhY2sgYSAjIGJhbGwgb2YgdGhlIHNhbWUgY29sb3IKICAgICAgICAgIAogICAgYmFsbCA8LSBiYWxsc1tzYW1wbGUoMTpsZW5ndGgoYmFsbHMpLCAxKV0gCiAgICBiYWxscyA8LSBjKGJhbGxzLCBiYWxsKQogICAgfSB9CiAgICBiYWxscyAKfQoKYWxwaGFfdmVjdCA8LSBjKDEsIDEwLCAxMDAsIDEwMDApCk5fdXJucyA8LSAzCnNpZ21hMiA8LSBjKDEsLjQsLjIpCk5fZHJhd3MgPC0gMTAwCk5feGF4aXMgPC0gMjAwCnhfYXhpcyA8LSBzZXEoLTMsIDMsIGxlbmd0aCA9IE5feGF4aXMpCnJlc3VsdCA8LSBOVUxMCiAgZm9yIChhbHBoYSBpbiBhbHBoYV92ZWN0KSB7CiAgICBQVSA8LSBwb2x5YV91cm5fbW9kZWwoZnVuY3Rpb24oKSBybm9ybSgxKSwgTl9kcmF3cywgYWxwaGEpCiAgICBmb3IgKHUgaW4gMTpOX3VybnMpIHsKICAgIHJlcyA8LSBtYXBwbHkoZnVuY3Rpb24obWVhbikgZG5vcm0oeF9heGlzLCByZXAobWVhbiwgTl94YXhpcyksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJlcChzaWdtYTJbdV0sIE5feGF4aXMpKSwgUFUpCiAgICByZXMgPC0gYXBwbHkocmVzLCAxLCBtZWFuKQogICAgbmV3X2RyYXcgPC0gY2JpbmQocmVzLCB4X2F4aXMsIGFscGhhLCBzaWdtYTJbdV0pCiAgICByZXN1bHQgPC0gcmJpbmQocmVzdWx0LCBuZXdfZHJhdykKfSB9CnJlc3VsdCA8LSBhcy5kYXRhLmZyYW1lKHJlc3VsdCkKbmFtZXMocmVzdWx0KSA8LSBjKCJkZW5zaXR5IiwgIngiLCAiYWxwaGEiLCAic2lnbWEyIikKRFBfbWl4dCA8LSBxcGxvdChkYXRhID0gcmVzdWx0LCB5ID0gZGVuc2l0eSwgeCA9IHgsCiAgICAgICAgICAgICAgICAgZ2VvbSA9IGMoImxpbmUiLCAiYXJlYSIpKSArCiAgZmFjZXRfZ3JpZChhbHBoYSB+IHNpZ21hMiwgbGFiZWxsZXIgPQogICAgICAgICAgICAgICBsYWJlbF9icXVvdGUocm93cyA9IGFscGhhID09IC4oYWxwaGEpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgY29scyA9IHNpZ21hXjIgPT0gLihzaWdtYTIpKSkgKwogIGFlcyhjb2xvciA9IGFzLmZhY3RvcihhbHBoYSkpICsKICB0aGVtZShsZWdlbmQucG9zaXRpb24gPSAibm9uZSIpCkRQX21peHQKYGBgCgoKCgoKCgoKCgpBZGQgYSBuZXcgY2h1bmsgYnkgY2xpY2tpbmcgdGhlICpJbnNlcnQgQ2h1bmsqIGJ1dHRvbiBvbiB0aGUgdG9vbGJhciBvciBieSBwcmVzc2luZyAqQ21kK09wdGlvbitJKi4KCldoZW4geW91IHNhdmUgdGhlIG5vdGVib29rLCBhbiBIVE1MIGZpbGUgY29udGFpbmluZyB0aGUgY29kZSBhbmQgb3V0cHV0IHdpbGwgYmUgc2F2ZWQgYWxvbmdzaWRlIGl0IChjbGljayB0aGUgKlByZXZpZXcqIGJ1dHRvbiBvciBwcmVzcyAqQ21kK1NoaWZ0K0sqIHRvIHByZXZpZXcgdGhlIEhUTUwgZmlsZSkuIAoKVGhlIHByZXZpZXcgc2hvd3MgeW91IGEgcmVuZGVyZWQgSFRNTCBjb3B5IG9mIHRoZSBjb250ZW50cyBvZiB0aGUgZWRpdG9yLiBDb25zZXF1ZW50bHksIHVubGlrZSAqS25pdCosICpQcmV2aWV3KiBkb2VzIG5vdCBydW4gYW55IFIgY29kZSBjaHVua3MuIEluc3RlYWQsIHRoZSBvdXRwdXQgb2YgdGhlIGNodW5rIHdoZW4gaXQgd2FzIGxhc3QgcnVuIGluIHRoZSBlZGl0b3IgaXMgZGlzcGxheWVkLgoK